package primary.code01_Sort;

/**
 * 递归方式获取最大值
 * a = 2  b = 2  d = 0
 * 复杂度：O(N)
 * <p>
 * master公式求解复杂度：
 * T(N) = a*T(N/b) + O(N^d)
 * 当log_{b}a < d时，O(N^d)；
 * 当log_{b}a > d时，O(N^{log_{b}a})；
 * 当log_{b}a = d时，O(N^d * logN)；
 */
public class Code06_GetMax {
    /**
     * 使用master公式计算时间复杂度
     * T(N) = 2*T(N/2) + O(1)
     * a = 2, b = 2, d = 0
     * 命中第二条，O(N)
     */
    private static int getMax(int[] arr, int l, int r) {
       if(l == r) {
           return arr[l];
       }
        int m = (l+r)/2;
        /*将一个大问题划分为小问题*/
       return Math.max(getMax(arr, 0,m),getMax(arr,m+1,r));
    }

    public static void main(String[] args) {
        int[] arr = {4, 57, 87, 23, 57, 8, 1, 587, 3, 89};
        int res = getMax(arr, 0, arr.length - 1);
        System.out.println(res);
    }
}
